package leetcode.medium.limit400;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class No373 {
    public static void main(String[] args) {
        int[] nums1 = new int[]{1, 7, 11};
        int[] nums2 = new int[]{2, 4, 6};
        System.out.println(new No373().kSmallestPairs(nums1, nums2, 3));
    }

    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>((o1, o2) -> {
            return (o1[0] + o1[1]) - (o2[0] + o2[1]);
        });
        for (int i = 0; i < nums1.length; i++) {
            queue.offer(new int[]{nums1[i], nums2[0], 0});
        }
        List<List<Integer>> res = new ArrayList<>();
        while (!queue.isEmpty() && k > 0) {
            int[] poll = queue.poll();
            k--;
            res.add(Arrays.asList(new Integer[]{poll[0], poll[1]}));
            int nextIndex = poll[2] + 1;
            if (nextIndex < nums2.length) {
                queue.offer(new int[]{poll[0], nums2[nextIndex], nextIndex});
            }
        }
        return res;
    }
}
